Corelab Seminar
2011-2012
Euripides Markou (UCG)
Black Hole Search with Finite Automata Scattered in Synchronous Rings and Tori
Abstract.
We consider the problem of locating a black hole in synchronous
anonymous
networks using indistinguishable finite state agents. A black hole is a
harmful node in the network that destroys any agent visiting that node
without leaving any trace. The objective is to locate the black hole
without
destroying too many agents. This is difficult to achieve when the agents
are
initially scattered in the network and are unaware of the location of
each
other. In contrast to previous results, we solve the problem using a
small
team of finite-state agents each carrying a constant number of identical
tokens that could be placed on the nodes of the network. Thus, all
resources
used in our algorithms are independent of the network size. We restrict
our
attention to ring and torus networks. We show lower bonus on the number
of
agents and tokens and we present deterministic algorithms that match
those
lower bounds.
This is a joint work with Jeremie Chalopin, Shantanu Das and Arnaud
Labourel
and part of this work has been presented at SIROCCO 2011 and DISC 2011.